Topological Sorting Algorithm
Topological Sorting Algorithm is a linear ordering technique used for directed graphs, where nodes represent tasks and edges represent dependencies between the tasks. It is mainly used to find a valid sequence of performing tasks, respecting the given dependencies. This algorithm is applicable only to Directed Acyclic Graphs (DAGs), meaning the graphs should have directed edges and no cycles. Topological sort has a wide range of applications in computer science, such as scheduling tasks with dependencies, determining the order of compilation tasks in a build system, and finding a valid sequence of courses in a curriculum with prerequisites.
The algorithm works by repeatedly selecting a node with no incoming edges, adding it to the sorted list, and then removing the node and its outgoing edges from the graph. This process continues until all the nodes are added to the sorted list, or there are no more nodes with no incoming edges, indicating the presence of a cycle in the graph. There are two common methods for implementing topological sorting: the Kahn's algorithm, which uses a queue to store the nodes with no incoming edges, and the Depth-First Search (DFS) based algorithm, which traverses the graph in a depth-first manner, marking nodes visited and adding them to the sorted list in the post-order traversal. Both algorithms have a time complexity of O(V+E), where V is the number of nodes and E is the number of edges in the graph.
/*
Petar 'PetarV' Velickovic
Algorithm: Topological Sorting
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#define MAX_N 5001
using namespace std;
typedef long long lld;
int n;
struct Node
{
vector<int> adj;
};
Node graf[MAX_N];
bool mark[MAX_N];
int indegree[MAX_N];
int toposort[MAX_N];
//Algoritam za topolosko sortiranje usmerenog grafa; moze se koristiti i za otkrivanje ciklusa
//Slozenost: O(V + E)
inline int TopoSort()
{
queue<int> S;
for (int i=0;i<n;i++) if (indegree[i] == 0) S.push(i);
int idx = 0;
while (!S.empty())
{
int idd = S.front();
S.pop();
toposort[idx++] = idd;
for (int i=0;i<graf[idd].adj.size();i++)
{
if (--indegree[graf[idd].adj[i]] == 0) S.push(graf[idd].adj[i]);
}
}
if (idx < n) return -1; // Cycle detected!
else return 0;
}
int main()
{
n = 8;
graf[7].adj.push_back(0);
graf[7].adj.push_back(5);
graf[7].adj.push_back(6);
graf[4].adj.push_back(5);
graf[3].adj.push_back(7);
graf[3].adj.push_back(4);
graf[2].adj.push_back(7);
graf[1].adj.push_back(4);
graf[1].adj.push_back(6);
indegree[0] = 1;
indegree[1] = 0;
indegree[2] = 0;
indegree[3] = 0;
indegree[4] = 2;
indegree[5] = 2;
indegree[6] = 2;
indegree[7] = 2;
TopoSort();
for (int i=0;i<n;i++) printf("%d ",toposort[i]);
printf("\n");
return 0;
}
